namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0100. 相同的树")]
    public class No0100_IsSameTree : AbsBaseTestItem
    {
        /*
        给定两个二叉树，编写一个函数来检验它们是否相同。
        如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
        */

        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
            {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }

        public override void OnTest()
        {
            Assert.TestExe(IsSameTree,
                new TreeNode(1)
                {
                    left = new TreeNode(2),
                    right = new TreeNode(3),
                },
                new TreeNode(1)
                {
                    left = new TreeNode(2),
                    right = new TreeNode(3),
                },
                true);

            Assert.TestExe(IsSameTree,
                new TreeNode(1)
                {
                    left = new TreeNode(2),
                },
                new TreeNode(1)
                {
                    right = new TreeNode(2),
                },
                false);

            Assert.TestExe(IsSameTree,
                new TreeNode(1)
                {
                    left = new TreeNode(2),
                    right = new TreeNode(1),
                },
                new TreeNode(1)
                {
                    left = new TreeNode(1),
                    right = new TreeNode(2),
                },
                false);
        }

        public bool IsSameTree(TreeNode p, TreeNode q)
        {
            if (p == null && q == null) return true;
            if (p == null || q == null) return false;
            return p.val == q.val && IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
        }
    }
}
